[CF1019E]Raining season

边权是一次函数，求m个时刻树上最远点对之间的距离。
考虑点分，每个点到根的距离都是一个一次函数，维护下凸包。
在合并凸包的时候可以维护全局答案凸包。应该使用启发式合并，但是由于常数原因放弃了。

#pragma GCC optimize(2)
#include <iostream>
#include <cstdio>
#include <set>
#include <vector>
#include <climits>
#define Pair pair<LL,LL>
#define mp(x,y) make_pair(x,y)
#define fi first
#define se second
using namespace std;
typedef long long LL;
const int MAXN=1e5+5;
const int MAXM=1e6+5;
struct Line {
    mutable LL k,b,p;//y=kx+b
    Line() {}
    Line(LL k,LL b,LL p):k(k),b(b),p(p){}
    bool operator<(const Line &res) const {return k<res.k;}
} anss[MAXN];
typedef multiset<Line>::iterator mlit;
typedef vector<Pair>::iterator vcit;
struct Data:multiset<Line> {
    inline LL fl(LL a,LL b) {
        if ((a^b)<0) return a/b-(a%b!=0);
        return a/b; 
    }
    inline bool check(iterator x,iterator y) {//pop y?
        if (y==end()) {x->p=INT_MAX;return false;}
        if (x->k == y->k) x->p=((x->b > y->b)?INT_MAX:INT_MIN);
        else x->p=fl(y->b - x->b, x->k - y->k);
        return x->p >= y->p;
    }
    inline void add(LL k,LL b) {
        mlit t=insert(Line(k,b,0)),y=t,x=t;
        y++;
        while (check(t,y)) erase(y++);
        if (t!=begin() && check(--x,t)) erase(t++),check(x,t);
        t=x;
        while (t!=begin() && (--x)->p >= t->p) erase(t++),check(x,t),t=x;
    }
} ans;
int head[MAXN],vet[MAXN*2],nxt[MAXN*2],num;
Pair w[MAXN*2];
int sz[MAXN],mxs[MAXN],rt;
bool vis[MAXN];
int n,m;
inline int read() {
    char ch=getchar();int sum=0;
    while (ch>'9' || ch<'0') ch=getchar();
    while (ch>='0' && ch<='9') sum=sum*10+ch-'0',ch=getchar();
    return sum;
}
void print(LL x) {
    if (x>9) print(x/10);
    putchar(x%10+'0');
}
inline void addedge(int x,int y,int k,int b) {
    num++;vet[num]=y;w[num]=mp(k,b);nxt[num]=head[x];head[x]=num;
    num++;vet[num]=x;w[num]=mp(k,b);nxt[num]=head[y];head[y]=num;
}
void getroot(int x,int fa,int tot) {
    sz[x]=1;mxs[x]=0;
    for (int e=head[x];e;e=nxt[e]) {
        int v=vet[e];
        if (v==fa || vis[v]) continue;
        getroot(v,x,tot);
        sz[x]+=sz[v];
        mxs[x]=max(mxs[x],sz[v]);
    }
    mxs[x]=max(mxs[x],tot-sz[x]);
    if (mxs[x]<mxs[rt]) rt=x;
}
void getpath(int x,int fa,LL k,LL b,Data &a) {
    int son=0;
    for (int e=head[x];e;e=nxt[e]) {
        int v=vet[e];
        if (v==fa || vis[v]) continue;
        getpath(v,x,k+w[e].fi,b+w[e].se,a);
        son++;
    }
    if (!son) a.add(k,b);
}
inline void update(Data &a,Data &b) {
    vector<Pair> vec1,vec2;
    for (mlit it=a.begin();it!=a.end();++it) {
        if (!vec1.empty() && (it->k)==vec1[vec1.size()-1].fi) {
            vec1[vec1.size()-1].se=max(vec1[vec1.size()-1].se,it->b);
        }
        else vec1.push_back(mp(it->k,it->b));
    }
    for (mlit it=b.begin();it!=b.end();++it) {
        if (!vec2.empty() && (it->k)==vec2[vec2.size()-1].fi) {
            vec2[vec2.size()-1].se=max(vec2[vec2.size()-1].se,it->b);
        }
        else vec2.push_back(mp(it->k,it->b));
    }
    LL s1=0,s2=0;
    while (s1<vec1.size() && s2<vec2.size()) {
        ans.add(vec1[s1].fi+vec2[s2].fi,vec1[s1].se+vec2[s2].se);
        if (s1+1==vec1.size()) s2++;
        else if (s2+1==vec2.size()) s1++;
        else {
            double x1=-(vec1[s1+1].se-vec1[s1].se)/(double)(vec1[s1+1].fi-vec1[s1].fi);
            double x2=-(vec2[s2+1].se-vec2[s2].se)/(double)(vec2[s2+1].fi-vec2[s2].fi);
            if (x1<x2) s1++;
            else s2++;
        }
    }
}
Data merge(int l,int r,vector<Data> &q) {
    if (l==r) {
        Data tt;
        tt.add(0,0);
        update(tt,q[0]);
        return q[l];
    }
    int mid=(l+r)>>1;
    Data t1=merge(l,mid,q),t2=merge(mid+1,r,q);
    if (t1.size()>t2.size()) swap(t1,t2);
    update(t1,t2);
    for (mlit it=t1.begin();it!=t1.end();++it) t2.add(it->k,it->b);
    return t2;
}
void solve(int x,int tot) {
    vis[x]=1;
    vector<Data> vec;
    Data blank;blank.add(0,0);
    for (int e=head[x];e;e=nxt[e]) {
        int v=vet[e];
        if (vis[v]) continue;
        vec.push_back(blank);
        getpath(v,x,w[e].fi,w[e].se,vec[vec.size()-1]);
    }
    if (!vec.empty()) merge(0,vec.size()-1,vec);
    for (int e=head[x];e;e=nxt[e]) {
        int v=vet[e];
        if (vis[v]) continue;
        rt=0;
        int tt=sz[v];
        if (tt>sz[x]) tt=tot-sz[x];
        getroot(v,x,tt);
        solve(rt,tt);
    }
}
int main() {
    n=read(),m=read();
    ans.add(0,0);
    for (int i=1;i<n;i++) {
        int x=read(),y=read(),k=read(),b=read();
        addedge(x,y,k,b);
    }
    mxs[0]=(n<<1);rt=0;
    getroot(1,0,n);
    solve(rt,n);
    int top=0;
    for (mlit it=ans.begin();it!=ans.end();++it) anss[++top]=(*it);
    for (LL i=0,j=1;i<m;i++) {
        while (anss[j].p<i) j++;
        print(anss[j].k*i+anss[j].b);putchar(' ');
    }
    return 0;
}